package algos_dasgupta;

import java.util.Arrays;

public class LongestIncreasingSubsequence {

	private int findLis(int[] seq) {
		int[] ans = new int[seq.length];
		
		ans[0] = 1;

		for(int i = 1; i < seq.length; i++) {
			int max = ans[i]; 
			for(int j = 0; j <= i; j++) {
				if(seq[j] < seq[i] && max < ans[j])
					max = ans[j];
			}
			ans[i] = max + 1;
		}
		System.out.println(Arrays.toString(ans));
		return max_array(ans);
		
	}
	
	private int max_array(int[] ans)
	{
		int max = Integer.MIN_VALUE;
		for(int a : ans)
			if(a > max)
				max = a;
		return max;
	}
	
	public static void main(String[] args) {
		LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
		int[] seq = {2,3,7,1,2,5,3,5};
		
		System.out.println(lis.findLis(seq));

	}

	

}
